package LeetCode刷题;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-11-12 14:40
 * @description: Functions of this class is
 * 题解：（其实就是和求最大深度一个意思的，但是如果左子树或者右子树有一个为空的话，则是不参与深度比较的）
 *
 * 叶子节点的定义是左孩子和右孩子都为 null 时叫做叶子节点
 * 当 root 节点左右孩子都为空时，返回 1
 * 当 root 节点左右孩子有一个为空时，返回不为空的孩子节点的深度
 * 当 root 节点左右孩子都不为空时，返回左右孩子较小深度的节点值
 *
 * class Solution {
 *     public int minDepth(TreeNode root) {
 *         // 求最小深度时将Math.max换成Math.min即可，
 *         //但要注意如果根节点的左或右子树为空的话是构不成子树的。
 *         //而最小深度是要求从根节点到子树的。当左或右子树为空时，不符合要求。
 *         if(root == null){
 *             return 0;
 *         }
 *         int leftMinDepth = minDepth(root.left);
 *         int rightMinDepth = minDepth(root.right);
 *         if(root.left == null && root.right != null){
 *             //假如左子树为空了，但是右子树还不为空，说明还没有到达叶子节点，要继续往下走，那么就继续递归不为空的那个节点
 *             return rightMinDepth + 1;
 *         }
 *         if(root.left != null && root.right == null){
 *             //假如右子树为空了，但是左子树还不为空，说明还没有到达叶子节点，要继续往下走，那么就继续递归不为空的那个节点
 *             return leftMinDepth + 1;
 *         }
 *         return Math.min(leftMinDepth, rightMinDepth) + 1;
 *     }
 * }
 *
 * ！！！！！！！！！！！二叉树的题目关键就是要抓住***递归形式*****前序后序中序这几种遍历就差不多的了！！！！！！！！
 * 更优解法：！！！！层序遍历！！！！！！！
 * class Solution {
 *     public int minDepth(TreeNode root) {
 *         int minDepth = 0;
 *         if (root == null) return minDepth;
 *         Queue<TreeNode> queue = new LinkedList<>();
 *         queue.add(root);
 *         while(!queue.isEmpty()) {
 *             int size = queue.size();
 *             for (int i = 0; i < size; i++) {
 *                 TreeNode node = queue.poll();
 *                 if (node.left != null) queue.add(node.left);
 *                 if (node.right != null) queue.add(node.right);
 *                 if (node.left == null && node.right == null) {
 *                     return minDepth+1;
 *                 }
 *             }
 *             minDepth++;
 *         }
 *         return minDepth;
 *     }
 * }
 **/
public class No二叉树的最小深度 {
//    private int ans=Integer.MAX_VALUE;
//    public int minDepth(TreeNode root) {
//        if(root!=null){
//            findMinDepth(root,1);
//            return ans;
//        }
//        return 0;
//    }
//    private void findMinDepth(TreeNode root,int depth){
//        if(root!=null){
//            findMinDepth(root.left,depth+1);
//            if(root.left==null&&root.right==null){
//                ans=Math.min(ans,depth);
//            }
//            findMinDepth(root.right,depth+1);
//        }
//    }
}